In a data network, network devices route data packets to other network devices. For example, a data network may include one or more core routers that carry packets tunneled to or from one or more edge routers. When a particular edge router fails or otherwise becomes unreachable, the core routers must reroute data packets that were originally intended for the failed edge router to another edge router. Typically, this requires either the core routers waiting for routing tables to be updated, or the core routers learning the prefixes that are reachable by each of the edge routers.